{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #省份数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findCircleNum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #省份数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<div class=\"original__bRMd\">\n",
    "<p>有 <code>n</code> 个城市，其中一些彼此相连，另一些没有相连。如果城市 <code>a</code> 与城市 <code>b</code> 直接相连，且城市 <code>b</code> 与城市 <code>c</code> 直接相连，那么城市 <code>a</code> 与城市 <code>c</code> 间接相连。</p>\n",
    "\n",
    "<p><strong>省份</strong> 是一组直接或间接相连的城市，组内不含其他没有相连的城市。</p>\n",
    "\n",
    "<p>给你一个 <code>n x n</code> 的矩阵 <code>isConnected</code> ，其中 <code>isConnected[i][j] = 1</code> 表示第 <code>i</code> 个城市和第 <code>j</code> 个城市直接相连，而 <code>isConnected[i][j] = 0</code> 表示二者不直接相连。</p>\n",
    "\n",
    "<p>返回矩阵中 <strong>省份</strong> 的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/graph1.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>isConnected = [[1,1,0],[1,1,0],[0,0,1]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>isConnected = [[1,0,0],[0,1,0],[0,0,1]]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 200</code></li>\n",
    "\t<li><code>n == isConnected.length</code></li>\n",
    "\t<li><code>n == isConnected[i].length</code></li>\n",
    "\t<li><code>isConnected[i][j]</code> 为 <code>1</code> 或 <code>0</code></li>\n",
    "\t<li><code>isConnected[i][i] == 1</code></li>\n",
    "\t<li><code>isConnected[i][j] == isConnected[j][i]</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 547&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/number-of-provinces/\">https://leetcode-cn.com/problems/number-of-provinces/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bLyHh0](https://leetcode.cn/problems/bLyHh0/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bLyHh0](https://leetcode.cn/problems/bLyHh0/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0],[1,1,0],[0,0,1]]', '[[1,0,0],[0,1,0],[0,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        qed = set()\n",
    "        count = 0\n",
    "        for i in range(len(isConnected)):\n",
    "            for j in range(len(isConnected[0])):\n",
    "                if isConnected[i][j]==1 and i not in qed:\n",
    "                    que = deque()\n",
    "                    que.append((i,j))\n",
    "                    qed.add(i)\n",
    "                    count+=1\n",
    "                    while que:\n",
    "                        node = que.popleft()\n",
    "                        (row,col) = node\n",
    "                        for k in range(len(isConnected[0])):\n",
    "                            if isConnected[col][k]==1 and k not in qed:\n",
    "                                que.append((col,k))\n",
    "                                qed.add(k)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "\n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        self.parent[rootx] = rooty\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if isConnected[i][j]:\n",
    "                    uf.union(i, j)\n",
    "        return sum(uf.parent[i] == i for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        cities = {i: None for i in range(n)}\n",
    "        checked_bag = {(i, j): None for i in range(n) for j in range(n)}\n",
    "\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        def method(frontier, group):\n",
    "            while frontier:\n",
    "                i = frontier.pop()\n",
    "                for j in range(n):\n",
    "                    checked_bag[(i, j)] = True\n",
    "                    if isConnected[i][j] is 1:\n",
    "                        if j not in frontier and cities[j] is None:\n",
    "                            frontier = [j] + frontier\n",
    "                        cities[i] = group\n",
    "                        cities[j] = group\n",
    "        group = 0\n",
    "        for i in range(n):\n",
    "            if cities[i] is None:\n",
    "                group += 1\n",
    "                method([i], group)\n",
    "        return group\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        connect_num = len(isConnected)\n",
    "        city_set = set()\n",
    "        ans = 0\n",
    "        left_city = set(x for x in range(connect_num))\n",
    "\n",
    "        def dfs(city: int):\n",
    "            nonlocal city_set\n",
    "            for i in list(left_city):\n",
    "                if isConnected[city][i] == 1 and i not in city_set:\n",
    "                    city_set.add(i)\n",
    "                    dfs(i)\n",
    "        while left_city:\n",
    "            city_num = left_city.pop()\n",
    "            dfs(city_num)\n",
    "            ans += 1\n",
    "            left_city = left_city.difference(city_set)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        connect_num = len(isConnected)\n",
    "        city_set = set()\n",
    "        ans = 0\n",
    "        left_city = set(x for x in range(connect_num))\n",
    "\n",
    "        def dfs(city: int):\n",
    "            nonlocal city_set\n",
    "            for i in list(left_city):\n",
    "                if isConnected[city][i] == 1 and i not in city_set:\n",
    "                    city_set.add(i)\n",
    "                    dfs(i)\n",
    "        while left_city:\n",
    "            city_num = left_city.pop()\n",
    "            dfs(city_num)\n",
    "            ans += 1\n",
    "            left_city = left_city.difference(city_set)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        N = len(isConnected)\n",
    "        connect = [set() for i in range(N)]\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    connect[i].add(j)\n",
    "        \n",
    "        searched = set()\n",
    "        def search(i):\n",
    "            stack = [i]\n",
    "            while len(stack) != 0:\n",
    "                i = stack.pop(0)\n",
    "                searched.add(i)\n",
    "                stack.extend(list(connect[i]-searched))\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            if i not in searched:\n",
    "                res += 1\n",
    "                search(i)\n",
    "        return res       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        cities = []\n",
    "        for i in range(len(isConnected)):\n",
    "            cities.append({i})\n",
    "        for y in range(len(isConnected)):\n",
    "            for x in range(len(isConnected[0])):\n",
    "                if isConnected[y][x] == 1:\n",
    "                    for i in range(len(cities)):\n",
    "                        if y in cities[i]:\n",
    "                            if x in cities[i]:\n",
    "                                break\n",
    "                            elif x not in cities:\n",
    "                                for j in range(len(cities)):\n",
    "                                    if x in cities[j]:\n",
    "                                        cities[i] = cities[i].union(cities[j])\n",
    "                                        cities.remove(cities[j])\n",
    "                                        break\n",
    "                            break\n",
    "        return len(cities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class UnionFind():\n",
    "#     def __init__(self, n):\n",
    "#         self.root = [i for i in range(n)]\n",
    "#         # self.size = [1 for i in range(n)]\n",
    "#         # self.part = n \n",
    "#     def find_root(self, i):\n",
    "#         return self.root[i]\n",
    "\n",
    "#     def union(self, a, b):\n",
    "#         x = self.find_root(a)\n",
    "#         y = self.find_root(b)\n",
    "#         if x==y:\n",
    "#             return False\n",
    "#         else:\n",
    "#             min_r = min(x, y) \n",
    "#             r = max(x, y)\n",
    "#             for i in range(len(self.root)):\n",
    "#                 if self.root[i] == r:\n",
    "#                     self.root[i] = min_r\n",
    "#         return True  \n",
    "#     def isConnected(self, a, b):\n",
    "#         return self.find_root(a)==self.find_root(b)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        # dfs\n",
    "        verts = [i for i in range(len(isConnected))]\n",
    "\n",
    "        visited = set()\n",
    "        def dfs(i):\n",
    "            if i in visited:\n",
    "                return None\n",
    "            self.cnt +=1 \n",
    "            visited.add(i)\n",
    "            for j, v in enumerate(isConnected[i]):\n",
    "                if v==1:\n",
    "                    dfs(j)\n",
    "        res = 0\n",
    "        for i in verts:\n",
    "            self.cnt = 0\n",
    "            dfs(i)\n",
    "            if self.cnt >0:\n",
    "                res +=1\n",
    "        return res \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # #BFS\n",
    "        # province = 0\n",
    "        # row = len(isConnected)\n",
    "        # visited = [0]*row \n",
    "        # for i in range(row):\n",
    "        #     if visited[i] ==0:\n",
    "        #         q = [i]\n",
    "        #         province +=1\n",
    "        #     for j in range(row):\n",
    "        #         conn = isConnected[i][j]\n",
    "        #         if conn==1:\n",
    "        #             q.append(j)\n",
    "        #             visited[j] = 1\n",
    "        #     while q:\n",
    "        #         len_ = len(q)\n",
    "        #         for _ in range(len_):\n",
    "        #             v = q.pop()\n",
    "        #             for c in range(row):\n",
    "        #                 if isConnected[v][c]==1 and visited[c]==0:\n",
    "        #                     q.append(c)\n",
    "        #                     visited[c] = 1\n",
    "        # return province\n",
    "\n",
    "        # #UNION FIND\n",
    "        # n = len(isConnected)\n",
    "        # uf = UnionFind(n)\n",
    "        # for i in range(len(isConnected)):\n",
    "        #     for j in range(len(isConnected[0])):\n",
    "        #         if i > j:\n",
    "        #             if isConnected[i][j]==1:\n",
    "        #                 uf.union(i, j)\n",
    "        # return len(set(uf.root))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        # 并查集\n",
    "        n = len(isConnected)\n",
    "        parent = list(range(n))\n",
    "        # 寻找属于哪一个联通分块\n",
    "        def find(i):\n",
    "            if parent[i] != i:\n",
    "                parent[i] = find(parent[i])  # 不断寻找自身的上级，即属于哪一个联通分块(寻找帮主)\n",
    "            return parent[i]\n",
    "        def union(i,j):\n",
    "            parent[find(i)] = find(j)  # 合并到联通分块,这里将i联通到j，(将i的帮主设为j的帮主)\n",
    "         \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    union(i, j)\n",
    "        \n",
    "        provinces = sum(parent[i] == i for i in range(n))  # parent[i] == i(即i为帮主，联通分块的老大)\n",
    "        return provinces\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        ans = 0\n",
    "        visited = [False] * n\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            ans += 1\n",
    "            visited[i] = True\n",
    "            q = [i]\n",
    "            while q:\n",
    "                t = q.pop(0)\n",
    "                for j in range(n):\n",
    "                    if isConnected[t][j] and not visited[j]:\n",
    "                        visited[j] = True\n",
    "                        q.append(j)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        counts = 0\n",
    "        vis = [0] * n\n",
    "\n",
    "        q = deque()\n",
    "\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                q.append(i)\n",
    "                while q:\n",
    "                    k = q.popleft()\n",
    "                    vis[k] = 1\n",
    "                    for j in range(n):\n",
    "                        if isConnected[k][j] == 1 and not vis[j]:\n",
    "                            q.append(j)\n",
    "                counts += 1\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        def tra(aR):\n",
    "            q = deque([aR])\n",
    "            while len(q) > 0:\n",
    "                p = q.popleft()\n",
    "                c = isConnected[p]\n",
    "                for i in range(n):\n",
    "                    if 1 == c[i]:\n",
    "                        c[i] = 2\n",
    "                        if i != p:\n",
    "                            q.append(i)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "           if 1 == isConnected[i][i]:\n",
    "               ret += 1\n",
    "               tra(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        q = collections.deque()\n",
    "        visited = [False for _ in range(len(isConnected))]\n",
    "        for i in range(len(isConnected)):\n",
    "            if not visited[i]:\n",
    "                ans += 1\n",
    "                visited[i] = True\n",
    "                q.append(i)\n",
    "                while q:\n",
    "                    city = q.popleft()\n",
    "                    for j in range(len(isConnected[city])):\n",
    "                        if isConnected[city][j] == 1:\n",
    "                            visited[j] = True\n",
    "                            q.append(j)\n",
    "                            isConnected[city][j] = 0\n",
    "        return ans\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "\n",
    "        def find_father(index):\n",
    "            if parent[index] == index:\n",
    "                return index\n",
    "            else:\n",
    "                parent[index] = find_father(parent[index])\n",
    "                return parent[index]\n",
    "        \n",
    "        def link_father(index, father):\n",
    "            parent[find_father(index)] = find_father(father)\n",
    "\n",
    "        parent = list(range(len(isConnected)))\n",
    "        for row in range(len(isConnected)):\n",
    "            for col in range(len(isConnected[0])):\n",
    "                if isConnected[row][col] == 1:\n",
    "                    link_father(col, row)\n",
    "        \n",
    "        ans = 0\n",
    "        for index, par in enumerate(parent):\n",
    "            if index == par:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        visited = set()\n",
    "        count = 0\n",
    "        for i in range(len(isConnected)):\n",
    "            if i not in visited:\n",
    "                self.dfs(isConnected, i, visited)\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, isConnected, i, visited):\n",
    "        visited.add(i)\n",
    "        for j in range(len(isConnected)):\n",
    "            if isConnected[i][j] == 1 and j not in visited:\n",
    "                self.dfs(isConnected, j, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        counts = 0\n",
    "        vis = [0] * n\n",
    "\n",
    "        q = deque()\n",
    "\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                q.append(i)\n",
    "                while q:\n",
    "                    k = q.popleft()\n",
    "                    vis[k] = 1\n",
    "                    for j in range(n):\n",
    "                        if isConnected[k][j] == 1 and not vis[j]:\n",
    "                            q.append(j)\n",
    "                counts += 1\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        num_provinces = 0\n",
    "        visited = [False] * n\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            num_provinces += 1\n",
    "            q, head = [i], -1\n",
    "            visited[i] = True\n",
    "            while head < len(q) - 1:\n",
    "                head += 1\n",
    "                for j in range(n):\n",
    "                    if isConnected[q[head]][j] == 1 and not visited[j]:\n",
    "                        visited[j] = True\n",
    "                        q.append(j)\n",
    "        return num_provinces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        p = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    union(i, j)\n",
    "\n",
    "        return sum(i == p[i] for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        c = len(isConnected)\n",
    "        visited = set()\n",
    "        p = 0\n",
    "        for i in range(c):\n",
    "            if i not in visited:\n",
    "                Q = collections.deque([i])\n",
    "                while Q:\n",
    "                    j = Q.popleft()\n",
    "                    visited.add(j)\n",
    "                    for k in range(c):\n",
    "                        if isConnected[j][k]==1 and k not in visited:\n",
    "                            Q.append(k)\n",
    "                p+=1\n",
    "        return p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        p = list(range(n))\n",
    "        count = n\n",
    "\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(a, b):\n",
    "            a, b = find(a), find(b)\n",
    "            if a == b:\n",
    "                return False\n",
    "            p[a] = b\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    if union(i, j):\n",
    "                        count -= 1\n",
    "\n",
    "        # return sum(i == p[i] for i in range(n))\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.merge_count=0\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if s[x]==x:return x\n",
    "\n",
    "            return find(s[x])\n",
    "            \n",
    "        def merge(x,y):\n",
    "            if find(x)!=find(y):\n",
    "            # if s[x]!=s[y]:\n",
    "                s[find(x)]=find(y)\n",
    "                self.merge_count+=1\n",
    "        \n",
    "        n=len(isConnected)\n",
    "        s=[i  for i in range(n)]\n",
    "        # merge_count=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j]==1:\n",
    "                    merge(i,j)\n",
    "        return n-self.merge_count\n",
    "                    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        level = 0\n",
    "        visited = [0] * n\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                visited[i] = 1\n",
    "                level += 1\n",
    "                stack = [i]\n",
    "                while stack:\n",
    "                    cur = stack.pop()\n",
    "                    for nex in range(n):\n",
    "                        if not visited[nex] and isConnected[cur][nex]:\n",
    "                           visited[nex] = 1\n",
    "                           stack.append(nex)\n",
    "        return level "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.fa = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.fa[fy] = fx\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        m = len(isConnected)\n",
    "        uf = UnionFind(m)\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    uf.union(i, j)\n",
    "        \n",
    "        ans = set()\n",
    "        for i in range(m):\n",
    "            ans.add(uf.find(i))\n",
    "\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        level = 0\n",
    "        visited = [0] * n\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                visited[i] = 1\n",
    "                level += 1\n",
    "                stack = [i]\n",
    "                while stack:\n",
    "                    cur = stack.pop()\n",
    "                    for nex in range(n):\n",
    "                        if not visited[nex] and isConnected[cur][nex]:\n",
    "                           visited[nex] = 1\n",
    "                           stack.append(nex)\n",
    "        return level "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n=len(isConnected)\n",
    "        par=[i for i in range(n)]\n",
    "        part=n\n",
    "        def find(x):\n",
    "            if par[x]==x:\n",
    "                return x\n",
    "            else:\n",
    "                return find(par[x])\n",
    "        def un(x,y):\n",
    "            rootx,rooty=find(x),find(y)\n",
    "            if rootx==rooty:\n",
    "                return False\n",
    "            par[rootx]=rooty\n",
    "            nonlocal part\n",
    "            part-=1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j]==1:\n",
    "                    un(i,j)\n",
    "        return part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        c = len(isConnected)\n",
    "        parent = list(range(c))\n",
    "\n",
    "        def find(index:int)->int:\n",
    "            if parent[index]!=index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1:int,index2:int):\n",
    "            parent[find(index1)]=find(index2)\n",
    "            \n",
    "        for i in range(c):\n",
    "            for j in range(i+1,c):\n",
    "                if isConnected[i][j]==1:\n",
    "                    union(i,j)\n",
    "        p = sum(parent[i]==i for i in range(c))\n",
    "        return p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        friends = len(isConnected)\n",
    "        counts = 0\n",
    "        visit = [0] * friends\n",
    "        for i in range(friends):\n",
    "            if not visit[i]:\n",
    "                self.dfs(i, friends, visit, isConnected)\n",
    "                counts += 1\n",
    "        return counts\n",
    "\n",
    "    # 深度优先搜索\n",
    "    def dfs(self, i, friends, visit, isConnected):\n",
    "        for j in range(friends):\n",
    "            if isConnected[i][j] == 1 and not visit[j]:\n",
    "                visit[j] = 1\n",
    "                self.dfs(j, friends, visit, isConnected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        p = {}\n",
    "\n",
    "        for k1, v1 in enumerate(isConnected):\n",
    "            p1 = p.setdefault(k1+1, [k1+1]) \n",
    "            for k2, v2 in enumerate(v1):\n",
    "                p2 = p.setdefault(k2+1, [k2+1])\n",
    "                if v2 == 1 and p1 != p2:\n",
    "                    p1.extend(p2)\n",
    "                    for c in p2:\n",
    "                        p[c] = p1\n",
    "        \n",
    "        tol = set()\n",
    "        for k, v in p.items():\n",
    "            tol.add(frozenset(v))\n",
    "        \n",
    "        return len(tol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        #初始化\n",
    "        n = len(isConnected) \n",
    "        uf = self.UnionFind(n) \n",
    "\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if isConnected[i][j] ==1:\n",
    "                    uf.union(i,j)\n",
    "        \n",
    "        return uf.count\n",
    "\n",
    "\n",
    "    class UnionFind:\n",
    "        def __init__(self, size):\n",
    "            self.root = {i: i for i in range(size)} # Data Struct {city, root} # value:int\n",
    "            self.rank = [0] * size\n",
    "            self.count = size\n",
    "\n",
    "        def find(self,x):\n",
    "            if x != self.root[x]:\n",
    "                self.root[x] = self.find(self.root[x])\n",
    "            return self.root[x]\n",
    "\n",
    "        def union(self, x, y):\n",
    "            root_x, root_y = self.find(x), self.find(y)  # key的value\n",
    "            if root_x != root_y:\n",
    "                if self.rank[root_x] > self.rank[root_y]:\n",
    "                    self.root[root_y] = root_x\n",
    "                elif self.rank[root_x] < self.rank[root_y]:\n",
    "                    self.root[root_x] = root_y\n",
    "                else:\n",
    "                    self.root[root_y] = root_x\n",
    "                    self.rank[root_x] += 1\n",
    "                self.count -= 1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        cities = len(isConnected)\n",
    "        parent = list(range(cities))\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            set_x = find(x)\n",
    "            set_y = find(y)\n",
    "            if set_x != set_y:\n",
    "                parent[set_x] = set_y\n",
    "            \n",
    "        for i in range(cities):\n",
    "            for j in range(i + 1, cities):\n",
    "                if isConnected[i][j] == 1 and i != j:\n",
    "                    union(i, j)\n",
    "        \n",
    "        ans = sum([parent[x] == x for x in range(cities)])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        count , n = 0 , len(isConnected[0])\n",
    "        vis = [False] * n\n",
    "        for i in range(n):\n",
    "            if vis[i] == False:\n",
    "                count += 1\n",
    "                que = [i]\n",
    "                while que:\n",
    "                    now = que.pop(0)\n",
    "                    vis[now] = True\n",
    "                    for j in range(n):\n",
    "                        if vis[j]==False and isConnected[now][j] == 1:\n",
    "                            que.append(j)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        dict1 = {}\n",
    "\n",
    "        for i in range(len(isConnected)):\n",
    "            for j in range(len(isConnected[0])):\n",
    "                if( isConnected[i][j] == 0):\n",
    "                    if( i not in dict1):\n",
    "                        dict1[i] = set([i]) \n",
    "                    if( j not in dict1):\n",
    "                        dict1[j] = set([j])\n",
    "                    \n",
    "                if( isConnected[i][j] == 1):\n",
    "                    if(i == 1 and j == 2):\n",
    "                        print(dict1, i,j)\n",
    "                    if( i in dict1 and j in dict1):\n",
    "                        set1 = dict1[i]\n",
    "                        set2 = dict1[j]\n",
    "                        res1 = set1 | set2\n",
    "                        if(i == 1 and j == 2):\n",
    "                            print(dict1, i,j, res1, dict1[i],dict1[j])\n",
    "                        for item in res1:\n",
    "                            dict1[item] = res1\n",
    "                    elif(i in dict1):\n",
    "                        dict1[i].add(j)\n",
    "                        dict1[j] = dict1[i]\n",
    "                    elif(j in dict1):\n",
    "                        dict1[j].add(i)\n",
    "                        dict1[i] = dict1[j]\n",
    "                    else:\n",
    "                        res1 = set([i,j])\n",
    "                        dict1[i] = res1 \n",
    "                        dict1[j] = res1\n",
    "        print(dict1)\n",
    "        resSet = set([])\n",
    "        for item in dict1:\n",
    "            resSet.add(id(dict1[item]))\n",
    "        return len(resSet)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        vitited = [False] * n\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            if not vitited[i]:\n",
    "                findCircle(isConnected, vitited, i)\n",
    "                result += 1\n",
    "        return result\n",
    "\n",
    "def findCircle(isConnected, vitited, i):\n",
    "    q = deque()\n",
    "    q.append(i)\n",
    "    vitited[i] = True\n",
    "    while q:\n",
    "        pos = q.popleft()\n",
    "        for f in range(len(isConnected)):\n",
    "            if isConnected[pos][f] == 1 and not vitited[f]:\n",
    "                q.append(f)\n",
    "                vitited[f] = True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        #初始化\n",
    "        n = len(isConnected) \n",
    "        uf = UnionFind(n) \n",
    "\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if isConnected[i][j] ==1:\n",
    "                    uf.union(i,j)\n",
    "        \n",
    "        return uf.count\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.root = {i: i for i in range(size)} # Data Struct {city, root} # value:int\n",
    "        self.rank = [0] * size\n",
    "        self.count = size\n",
    "    \n",
    "    def find(self,x):\n",
    "        if x != self.root[x]:\n",
    "            self.root[x] = self.find(self.root[x])\n",
    "        return self.root[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)  # key的value\n",
    "        if root_x != root_y:\n",
    "            if self.rank[root_x] > self.rank[root_y]:\n",
    "                self.root[root_y] = root_x\n",
    "            elif self.rank[root_x] < self.rank[root_y]:\n",
    "                self.root[root_x] = root_y\n",
    "            else:\n",
    "                self.root[root_y] = root_x\n",
    "                self.rank[root_x] += 1\n",
    "            self.count -= 1 \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        set_list = list()\n",
    "        for i in range(len(isConnected)):\n",
    "            set_list.append({i})\n",
    "\n",
    "        for m in range(len(isConnected)):\n",
    "            for n in range(len(isConnected[m])):\n",
    "                if m < n and isConnected[m][n] == 1:\n",
    "                    if isinstance(set_list[m], set):\n",
    "                        if isinstance(set_list[n], set):\n",
    "                            i = m\n",
    "                            j = n\n",
    "                        else:\n",
    "                            i = min(m, set_list[n])\n",
    "                            j = max(m, set_list[n])\n",
    "                    else:\n",
    "                        if isinstance(set_list[n], set):\n",
    "                            i = min(n, set_list[m])\n",
    "                            j = max(n, set_list[m])\n",
    "                        else:\n",
    "                            i = min(set_list[m], set_list[n])\n",
    "                            j = max(set_list[m], set_list[n])\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    set_list[i] = set_list[i].union(set_list[j])\n",
    "                    for idx in set_list[j]:\n",
    "                        set_list[idx] = i\n",
    "                    print(m, n, set_list)\n",
    "\n",
    "        cnt = 0\n",
    "        for each in set_list:\n",
    "            if isinstance(each, set):\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        fa = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if x == fa[x]: return x\n",
    "            return find(fa[x])\n",
    "        def union(x,y):\n",
    "            fx,fy = find(x),find(y)\n",
    "            fa[fx] = fy #x的父亲节点指向y 开始递归 \n",
    "        for i in range(n):\n",
    "            for j in range(i,n): #无向图 遍历一半就可以了\n",
    "                if isConnected[i][j] == 1: union(i,j)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if fa[i] == i: cnt+=1 #根节点的数量等于省份的数量\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        privinces = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                queue = collections.deque([i])\n",
    "                while queue:\n",
    "                    city = queue.popleft()\n",
    "                    visited.add(city)\n",
    "                    for c in range(n):\n",
    "                        if isConnected[city][c] == 1 and c not in visited:\n",
    "                            queue.append(c)\n",
    "                privinces += 1\n",
    "        return privinces\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        mp = [i for i in range(n)]\n",
    "        def find(loc):\n",
    "            print(loc)\n",
    "            if mp[loc] != loc:\n",
    "                mp[loc] = find(mp[loc])\n",
    "            return mp[loc]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j]:\n",
    "                    l,r = find(i),find(j)\n",
    "                    mp[l] = mp[r]\n",
    "        cnts = set(find(i) for i in range(n))\n",
    "        return len(cnts) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = list(range(n))\n",
    "\n",
    "    def find(self, node: int) -> int:\n",
    "        if self.root[node] != node:\n",
    "            self.root[node] = self.find(self.root[node])\n",
    "        return self.root[node]\n",
    "    \n",
    "    def union(self, node_a: int, node_b: int) -> None:\n",
    "        root_a = self.find(node_a)\n",
    "        root_b = self.find(node_b)\n",
    "        if root_a != root_b:\n",
    "            self.root[root_b] = root_a\n",
    "    \n",
    "    def isConnected(self, node_a: int, node_b: int) -> bool:\n",
    "        return self.find(node_a) == self.find(node_b)\n",
    "    \n",
    "    def group_num(self):\n",
    "        print(self.root)\n",
    "        return sum([self.root[i] == i for i in range(len(self.root))])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(isConnected)\n",
    "\n",
    "        union_find = UnionFind(n)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j]:\n",
    "                    union_find.union(i, j)\n",
    "\n",
    "        return union_find.group_num()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#python版本并查集\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "    \n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        \n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        \n",
    "        # while x != root:\n",
    "        #     original_father = self.father[x]\n",
    "        #     self.father[x] = root\n",
    "        #     x = original_father\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        uf = UnionFind()\n",
    "        n=len(isConnected)\n",
    "        for i in range(n):\n",
    "            uf.add(i)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and isConnected[i][j]==1:\n",
    "                    uf.merge(i, j)\n",
    "        \n",
    "        res=0\n",
    "        for son,father in uf.father.items():\n",
    "            if father==None:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        set_list = list()\n",
    "        for i in range(len(isConnected)):\n",
    "            set_list.append({i})\n",
    "\n",
    "        for m in range(len(isConnected)):\n",
    "            for n in range(len(isConnected[m])):\n",
    "                if m < n and isConnected[m][n] == 1:\n",
    "                    if isinstance(set_list[m], set):\n",
    "                        if isinstance(set_list[n], set):\n",
    "                            i = m\n",
    "                            j = n\n",
    "                        else:\n",
    "                            i = min(m, set_list[n])\n",
    "                            j = max(m, set_list[n])\n",
    "                    else:\n",
    "                        if isinstance(set_list[n], set):\n",
    "                            i = min(n, set_list[m])\n",
    "                            j = max(n, set_list[m])\n",
    "                        else:\n",
    "                            i = min(set_list[m], set_list[n])\n",
    "                            j = max(set_list[m], set_list[n])\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    set_list[i] = set_list[i].union(set_list[j])\n",
    "                    for idx in set_list[j]:\n",
    "                        set_list[idx] = i\n",
    "                    print(m, n, set_list)\n",
    "\n",
    "        cnt = 0\n",
    "        for each in set_list:\n",
    "            if isinstance(each, set):\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        if not isConnected:\n",
    "            return 0\n",
    "        \n",
    "        n = len(isConnected)\n",
    "        prov_cnt = 0\n",
    "        \n",
    "        neibor = defaultdict(set)  # https://www.jianshu.com/p/bbd258f99fd3\n",
    "        for row_idx, row in enumerate(isConnected):\n",
    "            for neib_idx, neib in enumerate(row):\n",
    "                if neib:\n",
    "                    neibor[row_idx].add(neib_idx)\n",
    "        \n",
    "        # print(neibor)            \n",
    "        \n",
    "        visited = set()\n",
    "        def dfs(num):\n",
    "            for neib in neibor[num]:\n",
    "                if neib not in visited:\n",
    "                    visited.add(neib)  # 染色\n",
    "                    dfs(neib)\n",
    "\n",
    "        for num in range(n):\n",
    "            if num not in visited:\n",
    "                prov_cnt += 1\n",
    "                dfs(num)\n",
    "\n",
    "        return prov_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        class DisjointSetUnion:\n",
    "\n",
    "            def __init__(self, n):\n",
    "                self.parent = [i for i in range(n)]\n",
    "\n",
    "            def find(self, x):\n",
    "                if self.parent[x] != x:\n",
    "                    self.parent[x] = self.find(self.parent[x])\n",
    "                return self.parent[x]\n",
    "            \n",
    "            def union(self, x, y):\n",
    "                px, py = self.find(x), self.find(y)\n",
    "                if px == py:\n",
    "                    return\n",
    "                self.parent[py] = px\n",
    "            \n",
    "        \n",
    "        n = len(isConnected)\n",
    "        dsu = DisjointSetUnion(n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j]:\n",
    "                    dsu.union(i, j)\n",
    "        for i in range(n):\n",
    "            dsu.find(i)\n",
    "        return len(set(dsu.parent))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#python版本并查集\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "    \n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        \n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        \n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        uf = UnionFind()\n",
    "        n=len(isConnected)\n",
    "        for i in range(n):\n",
    "            uf.add(i)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and isConnected[i][j]==1:\n",
    "                    uf.merge(i, j)\n",
    "        \n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if uf.father[i]==None:\n",
    "                res+=1\n",
    "        print(uf.father)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    O(n^2) / O(n)\n",
    "    '''\n",
    "    def findCircleNum_dfs(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces += 1\n",
    "        return provinces\n",
    "\n",
    "    '''\n",
    "    O(n^2) / O(n)\n",
    "    '''\n",
    "    def findCircleNum_bfs(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        from collections import deque\n",
    "        que = deque()\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                que.append(i)\n",
    "                while que:\n",
    "                    j = que.popleft()\n",
    "                    visited.add(j)\n",
    "                    for k in range(n):\n",
    "                        if k not in visited and isConnected[j][k] == 1:\n",
    "                            que.append(k)\n",
    "                provinces += 1\n",
    "\n",
    "        return provinces\n",
    "\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        # 路径压缩\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "\n",
    "        # 正常合并\n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        n = len(isConnected)\n",
    "        parent = list(range(n))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    union(i, j)\n",
    "\n",
    "        provinces = sum(parent[i] == i for i in range(n))\n",
    "        return provinces\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        # #多源dfs 遍历一个连通集合就加1 无向图\n",
    "        # res = 0\n",
    "        # visited = set()\n",
    "        \n",
    "        # def dfs(isConnected,i):\n",
    "        #     visited.add(i)\n",
    "        #     for j in range(len(isConnected[i])):\n",
    "        #         if isConnected[i][j] == 1 and j not in visited:\n",
    "        #             dfs(isConnected,j)\n",
    "                \n",
    "        # for i in range(len(isConnected)):\n",
    "        #     if i not in visited:\n",
    "        #             res += 1 #直接加1 dfs一次后相关连通分量的node会全部进入visited\n",
    "        #             dfs(isConnected,i)\n",
    "        # return res\n",
    "\n",
    "        #多源 bfs\n",
    "        # res = 0\n",
    "        # visited = set()\n",
    "        # queue = deque()\n",
    "        # for i in range(len(isConnected)):\n",
    "        #     if i not in visited:\n",
    "        #         queue.append(i)\n",
    "        #         while(queue):\n",
    "        #             node = queue.popleft()\n",
    "        #             visited.add(node)\n",
    "        #             for j in range(len(isConnected[node])):\n",
    "        #                 if isConnected[node][j] == 1 and j not in visited:\n",
    "        #                     queue.append(j)\n",
    "        #         res += 1\n",
    "        # return res\n",
    "\n",
    "        #并查集\n",
    "        father = [i for i in range(len(isConnected))]\n",
    "        #rank = [1 for _ in range(len(isConnected))] #\n",
    "\n",
    "        def find(i):\n",
    "            if father[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                # father[i] = find(father[i])\n",
    "                # return father[i]\n",
    "                return find(father[i])\n",
    "        \n",
    "        def union(i,j):\n",
    "            fai = find(i)\n",
    "            faj = find(j)\n",
    "            father[fai] = faj\n",
    "\n",
    "        for i in range(len(isConnected)):\n",
    "            for j in range(i+1,len(isConnected)):\n",
    "                if isConnected[i][j] == 1:\n",
    "                    union(i,j)\n",
    "        res = 0\n",
    "        print(father)\n",
    "        for i in range(len(isConnected)):\n",
    "            if father[i] == i:\n",
    "                res+=1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.label = False\n",
    "        self.neighbors = []\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def bfs(node):\n",
    "            q = []\n",
    "            q.append(node)\n",
    "            while len(q)!=0:\n",
    "                cur = q.pop()\n",
    "                cur.label = True\n",
    "                for nei in cur.neighbors:\n",
    "                    if not nei.label:\n",
    "                        q.append(nei)\n",
    "\n",
    "        nodeMap = {}\n",
    "        \n",
    "        for i in range(len(isConnected)):\n",
    "            nodeMap[i] = Node()\n",
    "\n",
    "        # 建图\n",
    "        for i in range(len(isConnected)):\n",
    "            for j in range(len(isConnected[0])):\n",
    "                if isConnected[i][j]==1:\n",
    "                    nodeMap[i].neighbors.append(nodeMap[j])\n",
    "        \n",
    "        # 计算\n",
    "        res = 0\n",
    "        for i in nodeMap.keys():\n",
    "            if not nodeMap[i].label:\n",
    "                res+=1\n",
    "                bfs(nodeMap[i])      \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected):\n",
    "        edges = defaultdict(list)\n",
    "        length = len(isConnected)\n",
    "        visited = [0] * length\n",
    "        count = 0\n",
    "        for i in range(length):\n",
    "            for j in range(length):\n",
    "                if not i == j and isConnected[i][j] == 1:\n",
    "                    edges[i].append(j)\n",
    "\n",
    "        def dfs(u: int):\n",
    "            visited[u] = 1\n",
    "            for v in edges[u]:\n",
    "                if not visited[v]:\n",
    "                    dfs(v)\n",
    "\n",
    "        for i in range(length):\n",
    "            if not visited[i]:\n",
    "                count += 1\n",
    "                dfs(i)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = [0] * n\n",
    "        def dfs(i):\n",
    "            if not visited[i]:\n",
    "                visited[i] = 1\n",
    "                for j in range(n):\n",
    "                    if isConnected[i][j]:\n",
    "                        dfs(j)\n",
    "        num = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                dfs(i)\n",
    "                num += 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        c = len(isConnected)\n",
    "        p = 0\n",
    "        visited = set()\n",
    "        def dfs(i:int):\n",
    "            for j in range(c):\n",
    "                if isConnected[i][j]==1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        for i in range(c):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                p+=1\n",
    "        return p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i: int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces += 1\n",
    "        \n",
    "        return provinces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i:int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j]==1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces+=1\n",
    "        return provinces\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i: int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces += 1\n",
    "        \n",
    "        return provinces\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = [0] * n  # 记录城市是否被访问过\n",
    "        \n",
    "        def dfs(city: int):\n",
    "            for i in range(n):\n",
    "                # 如果城市 i 和当前的城市相连，且未被访问过\n",
    "                if isConnected[city][i] == 1 and visited[i] == 0:\n",
    "                    visited[i] = 1\n",
    "                    dfs(i)\n",
    "        \n",
    "        provinces = 0\n",
    "        for i in range(n):\n",
    "            # 如果当前城市未被访问过，则从这个城市开始进行一次DFS\n",
    "            if visited[i] == 0:\n",
    "                dfs(i)\n",
    "                provinces += 1  # 完成一次DFS后，省份数增加1\n",
    "        \n",
    "        return provinces\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        connect = {}\n",
    "        for i in range(n):\n",
    "            connect[i] = connect.get(i,set())\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] == 1 and i!=j:\n",
    "                    connect[i].add(j)\n",
    "\n",
    "        seen = set()\n",
    "        def dfs(i):\n",
    "            seen.add(i)\n",
    "            for j in connect[i]:\n",
    "                if j not in seen:\n",
    "                    dfs(j)\n",
    "        ans= 0\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i: int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces += 1\n",
    "        \n",
    "        return provinces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i: int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces += 1\n",
    "        \n",
    "        return provinces\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(x):\n",
    "            for y in range(n):\n",
    "                if isConnected[x][y] == 1 and not y in visited:\n",
    "                    visited.add(y)\n",
    "                    dfs(y)\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # DFS. Time O(n) Space O(n)\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        vis = [False for _ in range(n)]\n",
    "        def dfs(i):\n",
    "            if vis[i]: return\n",
    "            vis[i] = True\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j]:\n",
    "                    dfs(j)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#   def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "#     n = len(isConnected)\n",
    "#     dsu = DSU(n)\n",
    "#     for i in range(n):\n",
    "#         for j in range(i, n):\n",
    "#             if isConnected[i][j] == 1:\n",
    "#                 dsu.union(i, j)\n",
    "#     return dsu.size()\n",
    "\n",
    "# class DSU:\n",
    "#     def __init__(self, n):\n",
    "#         self.pa = list(range(n))\n",
    "    \n",
    "#     def find(self, x):\n",
    "#         if self.pa[x] != x:\n",
    "#             self.pa[x] = self.find(self.pa[x])\n",
    "#         return self.pa[x]\n",
    "\n",
    "#     def union(self, x, y):\n",
    "#         self.pa[self.find(x)] = self.find(y)\n",
    "    \n",
    "#     def size(self):\n",
    "#         return sum(1 if self.pa[x] == x else 0 for x in range(len(self.pa)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        ic = isConnected\n",
    "\n",
    "        def dfs(i):\n",
    "            seen.add(i)\n",
    "            for i, nxt in enumerate(ic[i]):\n",
    "                if nxt == 1 and i not in seen:\n",
    "                    dfs(i)\n",
    "\n",
    "        n = len(ic)\n",
    "        seen = set()\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            def dfs(x):\n",
    "                visited[x] = 1\n",
    "                for y in range(n):\n",
    "                    if visited[y] == 0 and isConnected[x][y] == 1:\n",
    "                        dfs(y)\n",
    "                \n",
    "            n = len(isConnected)\n",
    "            visited = [0] * n\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if visited[i] == 0:\n",
    "                    res += 1\n",
    "                    dfs(i)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i: int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                provinces += 1\n",
    "        \n",
    "        return provinces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        n = len(isConnected)\n",
    "        visit = [0]*n\n",
    "\n",
    "        def dfs(index, visited):\n",
    "            if visited[index] == 1:\n",
    "                return\n",
    "            visited[index] = 1\n",
    "            for i in range(len(isConnected)):\n",
    "                if isConnected[index][i] == 1:\n",
    "                    dfs(i, visited)\n",
    "\n",
    "        for i in range(n):\n",
    "            if visit[i] == 0:\n",
    "                ans += 1 \n",
    "                dfs(i, visit)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i:int):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j]==1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        \n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        for i in range(cities):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        visited = [0] * len(isConnected)\n",
    "\n",
    "        def search(i, cur_ind):\n",
    "\n",
    "            for j in range(len(visited)):\n",
    "                if isConnected[i][j] == 0:\n",
    "                    continue\n",
    "                if visited[j] != 0:\n",
    "                    continue\n",
    "                visited[j] = cur_ind\n",
    "                search(j, cur_ind)\n",
    "            \n",
    "        for i in range(len(visited)):\n",
    "            cur_ind = max(visited) + 1\n",
    "            search(i, cur_ind)\n",
    "            \n",
    "        return max(visited)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        ##\n",
    "        cities = len(isConnected)\n",
    "        visited = set()\n",
    "        provinces = 0\n",
    "        for i in range(cities):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            dfs(i)\n",
    "            provinces += 1\n",
    "        ##\n",
    "        return provinces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UnionFind:\n",
    "        def __init__(self,data):\n",
    "            self.father = {}\n",
    "            for node in data:\n",
    "                self.father[node] = node\n",
    "\n",
    "        def find(self,node):\n",
    "            if node != self.father[node]:\n",
    "                self.father[node] = self.find(self.father[node])\n",
    "            return self.father[node]\n",
    "\n",
    "        def union(self,node1,node2):\n",
    "            self.father[self.find(node2)] = self.find(node1)\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        uf = Solution.UnionFind(range(n))\n",
    "        c = [(i,j) for j in range(n) for i in range(n) if isConnected[i][j] == 1 and i!=j]\n",
    "        for x,y in c:\n",
    "            uf.union(x,y)\n",
    "        ans = set()\n",
    "        for i in range(n):\n",
    "            ans.add(uf.find(i))\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        \n",
    "        def dfs(i):\n",
    "            for j in range(len(isConnected)):\n",
    "                if isConnected[i][j] and visited[j]==0:\n",
    "                    visited[j]=1\n",
    "                    dfs(j)\n",
    "            \n",
    "\n",
    "        visited=[0 for i in range(len(isConnected))]\n",
    "        sums=0\n",
    "        for i in range(len(isConnected)):\n",
    "            print(visited)\n",
    "            if not visited[i]:\n",
    "                dfs(i)\n",
    "                sums+=1\n",
    "        return sums\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            for j in range(citys):\n",
    "                if isConnected[i][j]==1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        citys=len(isConnected)\n",
    "        visited=set()\n",
    "        province=0\n",
    "        for i in range(citys):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                province+=1\n",
    "        return province                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        n = len(isConnected)\n",
    "        remain = {i for i in range(n)}\n",
    "        def dfs(city):\n",
    "            remain.remove(city)\n",
    "            for i in range(n):\n",
    "                if i in remain and isConnected[city][i] == 1:\n",
    "                    dfs(i)\n",
    "        for i in range(n):\n",
    "            if i in remain:\n",
    "                dfs(i)\n",
    "                count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            visited[i] = 1\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j] == 1 and not visited[j]:\n",
    "                    dfs(j)\n",
    "                    \n",
    "        cities = len(isConnected)\n",
    "        visited = [0] * cities\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(cities):\n",
    "            if not visited[i]:\n",
    "                count += 1\n",
    "                dfs(i)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        cnt = 0\n",
    "        checked = [False] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            checked[i] = True\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] and not checked[j]:\n",
    "                    checked[j] = True\n",
    "                    dfs(j)\n",
    "\n",
    "        for i in range(n):\n",
    "            if not checked[i]:\n",
    "                cnt += 1\n",
    "                dfs(i)\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        city = set()\n",
    "        count = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] == 1 and j not in city:\n",
    "                    city.add(j)\n",
    "                    dfs(j)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in city:\n",
    "                city.add(i)\n",
    "                dfs(i)\n",
    "                count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        numProvince = 0\n",
    "\n",
    "        def dfs(idx):\n",
    "            nonlocal n\n",
    "            for i in range(n):\n",
    "                if i not in visited and isConnected[idx][i]:\n",
    "                    visited.add(i)\n",
    "                    dfs(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                numProvince += 1\n",
    "                visited.add(i)\n",
    "                dfs(i)\n",
    "        \n",
    "        return numProvince"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            for j in range(cities):\n",
    "                if isConnected[i][j]==1 and j not in vis:\n",
    "                    vis.add(j)\n",
    "                    dfs(j)\n",
    "        cities=len(isConnected)\n",
    "        vis=set()\n",
    "        ans=0\n",
    "        for i in range(cities):\n",
    "            if i not in vis:\n",
    "                dfs(i)\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            for j in range(n):\n",
    "                if isConnected[i][j] == 1 and j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dfs(j)\n",
    "        n = len(isConnected)\n",
    "        visited = set()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
